/* vim: set tabstop=4 softtabstop=4 shiftwidth=4: */
/**
 * @file eight_puzzle.cpp
 * @author Yao Zongyou <yaozy2010@gmail.com>
 * @date 2010-12-23
 */

#include <assert.h>
#include <stdio.h>

#define MOVE_UP    -3
#define MOVE_DOWN  3
#define MOVE_LEFT  -1
#define MOVE_RIGHT 1

typedef struct node {
	int boxes[9];
	int level;
	node *p_next;
} node_t;

int cmp_node_boxes(node_t *p_node_1, node_t *p_node_2)
{
	return memcmp(p_node_1->boxes, p_node_2->boxes, sizeof(p_node_1->boxes));
}

void cpy_node_boxes(node_t *p_node_1, node_t *p_node_2)
{
	memcpy(p_node_2->boxes, p_node_1->boxes, sizeof(p_node_1->boxes));
}

int get_space(node_t *p_node)
{
	int i = 0;

	for (i = 0; i != 9; ++i) {
		if (p_node->boxes[i] == 0) {
			return i;
		}
	}

	assert(0);

	return 0;
}

int move_space(node_t *p_node_1, int direction, node_t *p_node_2)
{
	int space_before = get_space(p_node_1);
	int space_after = space_before + direction;
	if (space_after >= 0 && space_after < 9) {
		cpy_boxes(p_node_1, p_node_2);	
		p_node_2->boxes[space_before] = p_node_2->boxes[space_after];
		p_node_2->boxes[space_after] = 0;
		p_node_2->level = p_node_1->level + 1;

		return 0;
	} 

	return -1;
}

int bfs(node_t *p_node_start, node_t *p_node_end)
{
	if (cmp_node_boxes(p_node_start, p_node_end) == 0) {
		return 0;
	} else {
	}

	if (equal(start, end)) {
		return true;
	} else {
		int middle_up[9] = {0};
		int middle_down[9] = {0};
		int middle_left[9] = {0};
		int middle_right[9] = {0};
		
		int up = move_space(start, MOVE_UP, middle_up);
		int down = move_space(start, MOVE_DOWN, middle_down);
		int left = move_space(start, MOVE_LEFT, middle_left);
		int rigth = move_space(start, MOVE_RIGHT, middle_right);

		if (up) {
			if (equal(middle_up, end)) {
				return true;
			}
		}
		if (down) {
			if (equal(middle_down, end)) {
				return true;
			}
		}
		if (left) {
			if (equal(middle_left, end)) {
				return true;
			}
		}
		if (right) {
			if (equal(middle_right, end)) {
				return true;
			}
		}
		if (up) {
			if (bfs(middle_up, end)) {
				return true;
			}
		}
		if (down) {
			if (bfs(middle_down, end)) {
				return true;
			}
		}
		if (left) {
			if (bfs(middle_left, end)) {
				return true;
			}
		}
		if (right) {
			if (bfs(middle_right, end)) {
				return true;
			}
		}
	}

	return false;
}

int main(int argc, char **argv)
{
	int number = 0;
//	cin >> number;
//	cin.get();

	int i = 0;

	for (i = 0; i != number; ++i) {
		int start[9] = {0};
		int end[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8};

//		cout << "Case" << i + 1 << ":" << endl;
		char buffer[10] = {0};
//		cin.getline(buffer, sizeof(buffer));                  // 取棋盘信息
		int j = 0;
		for (j = 0; j < 9; ++j) {                // 输入初始状态
			start[j] = buffer[j] - 48;
		}

		if (!bfs(start, end)) {
//			cout << "IMPOSSIBLE" << endl;
		} else {
//			cout << "SUCCESS" << endl;
		}
	}

	return 0;
}
